package com.learn.algorithm.sort;

import java.util.Arrays;

/**
 * 插入排序
 *
 * @author wangxing
 * @version 2020/5/16 22:05 Administrator
 */
public class InsertSort {
    public static int[] sortSToB(int[] arr) {
        int l = arr.length;
//        时间复杂度O(n^2)
//        最好情况下O(n)已经基本有序的情况下
        for (int i = 1; i < l; i++) {
            //第一个位置(o位置)是单独一个,其自身为有序的,后续的数据时根据第一个位置去插入对比的
            // 所以从第2个位置开始进行插入排序的判定
            int data = arr[i];
            int j = i - 1;
//            与当前位置之前的所有位置数据进行对比
            for (; j >= 0; j--) {
//                当出现当前数据小于该位置之前的数据,则将这个位置的数据后移
                if (arr[j] > data) {
                    arr[j + 1] = arr[j];
                } else {
                    break;
                }
            }
//            直到出现比要排序位置数据小的时候,将该数据插入到这个位置
            arr[j + 1] = data;
//            System.out.println(Arrays.toString(arr));
        }
        return arr;
    }

}
